#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


SEG_MAX = 2 ** 32


# =================== return min =====================
def build_segment_tree(seg_tree, seg_idx, nums, start, end):
    # [start, end) 开闭区间
    assert end > start

    if start + 1 == end:
        seg_tree[seg_idx] = nums[start]
        return seg_tree[seg_idx]

    mid = (start + end + 1) // 2
    left_min  = build_segment_tree(seg_tree, seg_idx*2+1, nums, start, mid)
    right_min = build_segment_tree(seg_tree, seg_idx*2+2, nums, mid, end)

    seg_tree[seg_idx] = min(left_min, right_min)
    return seg_tree[seg_idx]

def query_min(start, end, nums_len, seg_tree):
    # 询问[start, end]闭区间最小值
    assert end < nums_len

    # 开区间变闭区间
    return _query_rec(start, end+1, seg_tree, 0, 0, nums_len)

def _query_rec(start, end, seg_tree, seg_idx, tree_start, tree_end):
    if start <= tree_start and end >= tree_end:
        # query overlap seg tree: 完全相关
        return seg_tree[seg_idx]

    elif start >= tree_end or end <= tree_start:
        # query no overlap seg tree: 完全无关
        return SEG_MAX
    else:
        # query partial overlap seg tree(可能seg tree rage overlap query rage)
        mid = (tree_start + tree_end + 1) // 2
        left_min  = _query_rec(start, end, seg_tree, seg_idx*2+1, tree_start, mid)
        right_min = _query_rec(start, end, seg_tree, seg_idx*2+2, mid, tree_end)
        return min(left_min, right_min)

def test_build():
    # nums = [1, -2, 3, -4, 5, -6, 7]
    # nums = [1, -2, 3, -4, 5, -6]
    nums = [1, -2, 3, -4, 5, -6]
    # tree_size = len(nums) * 2 -1      # 如果按照这个数量来建立: 因为有空节点, 无法按照heap数组方式构建segment tree
    tree_size = len(nums) * 4           # 最坏情况是4倍长度. 不知道如何证明!
    seg_tree = tree_size * [None]
    # print(len(seg_tree))

    build_segment_tree(seg_tree, 0, nums, 0, len(nums))
    # print(seg_tree)

    min = query_min(2, 4, len(nums), seg_tree)
    min = query_min(0, 0, len(nums), seg_tree)
    min = query_min(1, 1, len(nums), seg_tree)
    min = query_min(1, 3, len(nums), seg_tree)
    print(min)

# =================== return min index =====================
def build_segment_tree_idx(seg_tree, seg_idx, nums, start, end):
    # [start, end) 开闭区间
    assert end > start

    if start + 1 == end:
        seg_tree[seg_idx] = start
        return seg_tree[seg_idx]

    mid = (start + end + 1) // 2
    left_min_idx  = build_segment_tree_idx(seg_tree, seg_idx*2+1, nums, start, mid)
    right_min_idx = build_segment_tree_idx(seg_tree, seg_idx*2+2, nums, mid, end)

    if nums[left_min_idx] <= nums[right_min_idx]:
        seg_tree[seg_idx] = left_min_idx
    else:
        seg_tree[seg_idx] = right_min_idx

    return seg_tree[seg_idx]

def query_min_idx(start, end, nums, seg_tree):
    # 询问[start, end]闭区间最小值在nums中索引
    nums_len = len(nums)
    assert end < nums_len

    # 开区间变闭区间
    return _query_rec_idx(start, end+1, seg_tree, 0, 0, nums_len, nums)

def _query_rec_idx(start, end, seg_tree, seg_idx, tree_start, tree_end, nums):
    if start <= tree_start and end >= tree_end:
        # query overlap seg tree: 完全相关
        return seg_tree[seg_idx]

    elif start >= tree_end or end <= tree_start:
        # query no overlap seg tree: 完全无关
        return None       # -1索引, 即最后一个元素中存放着一个很大的数
    else:
        # query partial overlap seg tree(可能seg tree rage overlap query rage)
        mid = (tree_start + tree_end + 1) // 2
        left_min_idx  = _query_rec_idx(start, end, seg_tree, seg_idx*2+1, tree_start, mid, nums)
        right_min_idx = _query_rec_idx(start, end, seg_tree, seg_idx*2+2, mid, tree_end, nums)
        # return min(left_min, right_min)
        if left_min_idx is None:
            return right_min_idx

        if right_min_idx is None:
            return left_min_idx

        if nums[left_min_idx] <= nums[right_min_idx]:
            return left_min_idx
        else:
            return right_min_idx

def test_build_idx():
    # nums = [1, -2, 3, -4, 5, -6, 7]
    # nums = [1, -2, 3, -4, 5, -6]
    nums = [1, -2, 3, -4, 5, -6]
    tree_size = len(nums) * 4 + 1           # 最坏情况是4倍长度. 不知道如何证明!
    seg_tree = tree_size * [None]
    seg_tree[-1] = SEG_MAX

    build_segment_tree_idx(seg_tree, 0, nums, 0, len(nums))
    print(seg_tree)

    min = query_min_idx(3, 3, nums, seg_tree)
    min = query_min_idx(0, 0, nums, seg_tree)
    min = query_min_idx(1, 1, nums, seg_tree)
    min = query_min_idx(1, 3, nums, seg_tree)
    min = query_min_idx(1, 2, nums, seg_tree)
    print(min)


# def seg_tree_size(nums_size):
#     if nums_size in [0, 1]:
#         return nums_size

#     first  = (nums_size + 1) // 2
#     second = nums_size - first

#     return seg_tree_size(first) + seg_tree_size(second) + 1

def main():
    print("start main")
    # test_build()
    test_build_idx()

if __name__ == "__main__":
    main()
